//
//  Problem787.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/2/19.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 787. K 站中转内最便宜的航班
 有 n 个城市通过 m 个航班连接。每个航班都从城市 u 开始，以价格 w 抵达 v。

 现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到从 src 到 dst 最多经过 k 站中转的最便宜的价格。 如果没有这样的路线，则输出 -1。

 示例 1：
     输入:
     n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
     src = 0, dst = 2, k = 1
     输出: 200
     解释:
     城市航班图如下

     从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200，如图中红色所示。
 
 示例 2：
     输入:
     n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
     src = 0, dst = 2, k = 0
     输出: 500
     解释:
     城市航班图如下

     从城市 0 到城市 2 在 0 站中转以内的最便宜价格是 500，如图中蓝色所示。

 提示：
     n 范围是 [1, 100]，城市标签从 0 到 n - 1
     航班数量范围是 [0, n * (n - 1) / 2]
     每个航班的格式 (src, dst, price)
     每个航班的价格范围是 [1, 10000]
     k 范围是 [0, n - 1]
     航班没有重复，且不存在自环
 */
@objcMembers class Problem787: NSObject {
    func solution() {
        print(findCheapestPrice(3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 1))
        print(findCheapestPrice(3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 0))
    }
    
    /*
     动态规划
     1: 创建一个二维数组 price[n][K]
     2: price[i][j]: src作为起始点，src到达i点，最多经过j次中转话费的最小费用
     3: 特例：src作为起点，所以price[src][j]这一行的意思是：从src到src，根本不需要花费，都是0
     4: 特例：遍历flights，找到src作为起点-->flight[1]的所有值，那么price[flight[1]][0] = flight[2]
     5: 遍历flights，flight(i->j, p),  我们知道了 从i->j需要花费p
        那么我们求一下 src->j, 求在0...K情况下 所需要花费的最小
        dp[j][k] = min(dp[i][k-1] + flight[2], dp[j][k])
     */
    func findCheapestPrice(_ n: Int, _ flights: [[Int]], _ src: Int, _ dst: Int, _ K: Int) -> Int {
        if K == 0 {
            for flight in flights {
                if flight[0] == src, flight[1] == dst {
                    return flight[2]
                }
            }
            return -1
        }
        
        var price = Array(repeating: Array(repeating: Int.max, count: K+1), count: n)
        
        // 特例：src作为起点，所以price[src][j]这一行的意思是：从src到src，根本不需要花费，都是0
        for i in 0...K {
            price[src][i] = 0
        }
        
        // 特例：遍历flights，找到src作为起点-->flight[1]的所有值，那么price[flight[1]][0] = flight[2]
        for flight in flights {
            if flight[0] == src {
                price[flight[1]][0] = flight[2]
            }
        }
        print(price)
        
        for k in 1...K {        // 依次求出从src作为起点 到达i(0...n)，需要1次、2次最小费用
            for flight in flights {
                // 我知道 从start到end的花费，那么我想从src到end最小花费是多少呢？
                // 有2中可能性，
                // 1：有一条从src到end的路径price[end][k] 有具体的值
                //    没有从src到end的路径price[end][k] == Int.max
                // 2: 有一条从src到start的路径price[start][k-1] 有具体的值 + flight[2]
                //    没有从src到start的路径:price[start][k-1] == Int.max，所以这个flight是条废路径，
                let start = flight[0]
                let end = flight[1]
                print(start, end, price[start][k-1])
                if price[start][k-1] != Int.max {
                    
                    price[end][k] = min(price[start][k-1] + flight[2], price[end][k])
                }
            }
        }
        
        return price[dst][K] == Int.max ? -1 : price[dst][K]
    }
}
